/**
 * PROBLEM URL: http://community.topcoder.com/stat?c=problem_statement&pm=10943&rd=14546
 
Given a string of parentheses, you must turn it into a well formed string by inserting as few parentheses as possible, at any position (you cannot delete or change any of the existing parentheses).

A well formed string of parentheses is defined by the following rules:

The empty string is well formed.
If s is a well formed string, (s) is a well formed string.
If s and t are well formed strings, their concatenation st is a well formed string.
As examples, "(()())", "" and "(())()" are well formed strings and "())(", "()(" and ")" are malformed strings.
Given a String par of parentheses, return the minimum number of parentheses that need to be inserted to make it into a well formed string.


Definition

Class:	MissingParentheses
Method:	countCorrections
Parameters:	String
Returns:	int
Method signature:	int countCorrections(String par)
(be sure your method is public)


Constraints
-	par will contain between 1 and 50 characters, inclusive.
-	Each character of par will be an opening or closing parenthesis, i.e., '(' or ')'.
 * 
 */

package topcoder;

public class MissingParentheses {

	public int countCorrections(String par) {
		int r = 0, c = 0, o = 0;
		for (char ch : par.toCharArray()) {
			if (ch == '(')
				o++;
			else
				c++;
			if (c > o) {
				r++;
				o++;
			}
		}
		return r + o - c;
	}
}
